/*
 * Copyright (c) 2022 Hong Jiahua
 * https://gitee.com/arrco/jh_XOR_list
 * 
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 * 
 * The above copyright notice and this permission notice shall be included in all
 * copies or substantial portions of the Software.
 * 
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 */
#ifndef __JH_XOR_LIST_H__
#define __JH_XOR_LIST_H__

/************************************************************************/
/*                                                                      */
/************************************************************************/
typedef struct jh_xor_list_t{
    struct jh_xor_list_t* xorptr;
} jh_xor_list_t;

typedef struct {
    jh_xor_list_t* head;
    jh_xor_list_t* tail;
} jh_xor_list_base_t;

#define JH_XOR_LIST_XOR(x, y) ((jh_xor_list_t *)((size_t)(x) ^ (size_t)(y)))
#define JH_OFF_SET_OF(type, member) ((size_t)&((type *)0)->member)
#define JH_XOR_LIST_ENTRY(item, type, member) ((type *)((char *)(item) - JH_OFF_SET_OF(type, member)))

/**
 * 
 * @par Description:
 * 链表初始化
 * 
 * @param list      链表头
 * 
 * @retval None.
 * 
 */
static inline void jh_xor_list_init_head(jh_xor_list_base_t *list)
{
    list->head = NULL;
    list->tail = NULL;
}

/**
 * 
 * @par Description:
 * 链表是否为空
 * 
 * @param list      链表头
 * 
 * @retval TRUE     链表为空.
 * @retval FALSE    链表不为空.
 * 
 */
static inline int jh_xor_list_is_empty(jh_xor_list_base_t *list)
{
    return list->head == NULL && list->tail == NULL;
}

/**
 * 
 * @par Description:
 * 向链表中添加结点
 * 
 * @param list      链表头
 * @param prev      要添加的上一个链表结点地址
 * @param next      要添加的下一个链表结点地址
 * @param node      要添加的链表结点地址
 * 
 * @retval None.
 * 
 */
static inline void jh_xor_list_add(jh_xor_list_base_t *list, jh_xor_list_t *prev, jh_xor_list_t *next, jh_xor_list_t *node)
{
    if(node == NULL)
        return;
    
    jh_xor_list_t *side1 = prev ? : next;
    jh_xor_list_t *side2 = (side1 == prev) ? next : prev;
    
    if(side1 == NULL) {
        node->xorptr = JH_XOR_LIST_XOR(NULL, NULL);
        list->head = node;
        list->tail = node;
    } else if(side2 == NULL) {
        node->xorptr = JH_XOR_LIST_XOR(NULL, side1);
        side1->xorptr = JH_XOR_LIST_XOR(node, JH_XOR_LIST_XOR(NULL, side1->xorptr));
        
        if(side1 == list->head)
            list->head = node;
        else
            list->tail = node;
    } else {
        node->xorptr = JH_XOR_LIST_XOR(side1, side2);
        side1->xorptr = JH_XOR_LIST_XOR(JH_XOR_LIST_XOR(side1->xorptr, side2), node);
        side2->xorptr = JH_XOR_LIST_XOR(node, JH_XOR_LIST_XOR(side1, side2->xorptr));
    }
}

/**
 * 
 * @par Description:
 * 向链表头中添加结点
 * 
 * @param list      链表头
 * @param node      要添加的链表结点地址
 * 
 * @retval None.
 * 
 */
static inline void jh_xor_list_head_insert(jh_xor_list_base_t *list, jh_xor_list_t *node)
{
    if(list->head == NULL && list->tail == NULL) {
        node->xorptr = JH_XOR_LIST_XOR(NULL, NULL);
        list->head = node;
        list->tail = node;
    } else {
        node->xorptr = JH_XOR_LIST_XOR(NULL, list->head);
        list->head->xorptr = JH_XOR_LIST_XOR(node, JH_XOR_LIST_XOR(NULL, list->head->xorptr));
        list->head = node;
    }
}

/**
 * 
 * @par Description:
 * 向链表尾中添加结点
 * 
 * @param list      链表头
 * @param node      要添加的链表结点地址
 * 
 * @retval None.
 * 
 */
static inline void jh_xor_list_tail_insert(jh_xor_list_base_t *list, jh_xor_list_t *node)
{
    if(list->head == NULL && list->tail == NULL) {
        node->xorptr = JH_XOR_LIST_XOR(NULL, NULL);
        list->head = node;
        list->tail = node;
    } else {
        node->xorptr = JH_XOR_LIST_XOR(list->tail, NULL);
        list->tail->xorptr = JH_XOR_LIST_XOR(JH_XOR_LIST_XOR(list->tail->xorptr, NULL), node);
        list->tail = node;
    }
}

/**
 * 
 * @par Description:
 * 从链表中删除结点
 * 
 * @param list      链表头
 * @param node      要删除的链表结点地址
 * @param other     要删除的链表结点旁边的结点地址（上一个结点或者下一个结点地址）
 * 
 * @retval None.
 * 
 */
static inline void jha_xor_list_delete(jh_xor_list_base_t *list, jh_xor_list_t *node, jh_xor_list_t *other)
{
    if(node == NULL)
        return;
    
    jh_xor_list_t *side1 = other ? : JH_XOR_LIST_XOR(node->xorptr, other);
    jh_xor_list_t *side2 = (side1 == other) ? JH_XOR_LIST_XOR(node->xorptr, other) : other;
    
    if(side1 == NULL) {
        list->head = NULL;
        list->tail = NULL;
    } else if(side2 == NULL) {
        jh_xor_list_t** tmp = (node == list->head) ? &(list->head) : &(list->tail);
        *tmp = side1;
        (*tmp)->xorptr = JH_XOR_LIST_XOR(NULL, JH_XOR_LIST_XOR(node, (*tmp)->xorptr));
    } else {
        side1->xorptr = JH_XOR_LIST_XOR(JH_XOR_LIST_XOR(side1->xorptr, node), side2);
        side2->xorptr = JH_XOR_LIST_XOR(side1, JH_XOR_LIST_XOR(node, side2->xorptr));
    }
}

/**
 * 
 * @par Description:
 * 从链表中删除并返回头结点的地址
 * 
 * @param list  链表
 * 
 * @retval node 结点地址
 * 
 */
static inline jh_xor_list_t* jha_xor_list_remove_head(jh_xor_list_base_t *list)
{
    jh_xor_list_t *node = list->head;
    list->head = list->head ? JH_XOR_LIST_XOR(NULL, list->head->xorptr) : NULL;
    if(list->head)
        list->head->xorptr = JH_XOR_LIST_XOR(NULL, JH_XOR_LIST_XOR(node, list->head->xorptr));
    else
        list->tail = NULL;
    return node;
}

/**
 * 
 * @par Description:
 * 从链表中删除并返回尾结点的地址
 * 
 * @param list  链表
 * 
 * @retval node 结点地址
 * 
 */
static inline jh_xor_list_t* jha_xor_list_remove_tail(jh_xor_list_base_t *list)
{
    jh_xor_list_t *node = list->tail;
    list->tail = list->tail ? JH_XOR_LIST_XOR(list->tail->xorptr, NULL) : NULL;
    if(list->tail)
        list->tail->xorptr = JH_XOR_LIST_XOR(JH_XOR_LIST_XOR(list->tail->xorptr, node), NULL);
    else
        list->head = NULL;
    return node;
}

/**
 * 
 * @par Description:
 * 定义并初始化链表头
 * 
 * @param list      链表头名称
 * 
 * @retval None.
 * 
 */
#define JH_XOR_LIST_HEAD(list) jh_xor_list_base_t list = { NULL, NULL }

/**
 * 
 * @par Description:
 * 添加结点
 * 
 * @param item  结点地址，添加的结点会添加在其之后
 * @param list  链表头
 * @param node  结点地址，要添加的链表结点地址
 * 
 * @retval None.
 * 
 */
#define JH_XOR_LIST_ADD_NODE(__item, __list, __node)    \
    jh_xor_list_add(__list, __item, JH_XOR_LIST_XOR((__item)->xorptr, __prev), __node);

/**
 * 
 * @par Description:
 * 删除结点
 * 
 * @param item  结点地址，要被从链表中删除的结点地址
 * @param list  链表头
 * 
 * @retval None.
 * 
 */
#define JH_XOR_LIST_DEL_NODE(__item, __list)    \
    jha_xor_list_delete(__list, __item, __prev);

/**
 * 
 * @par Description:
 * 遍历链表
 * 
 * @param item  结点名
 * @param list  链表头
 * 
 * @retval None.
 * 
 */
#define JH_XOR_LIST_FOR_EACH(__item, __list)                                                \
    for (jh_xor_list_t *__item = (__list)->head, *__prev = NULL, *__tmp;                    \
         __item != NULL;                                                                    \
         __tmp = __item, __item = JH_XOR_LIST_XOR(__prev, __item->xorptr), __prev = __tmp)

/**
 * 
 * @par Description:
 * 安全的遍历链表，可以在遍历中添加与删除结点
 * 
 * @param item  结点名
 * @param list  链表头
 * 
 * @retval None.
 * 
 */
#define JH_XOR_LIST_FOR_EACH_SAFE(__item, __list)                                                                                                                                                           \
    for (jh_xor_list_t *__item = (__list)->head, *__prev = NULL, *__next = __item ? JH_XOR_LIST_XOR(NULL, __item->xorptr) : NULL, *__nextnext = __next ? JH_XOR_LIST_XOR(__item, __next->xorptr) : NULL;    \
         __item != NULL;                                                                                                                                                                                    \
         __item = __next, __next = __nextnext, __nextnext = __next ? JH_XOR_LIST_XOR(__item, __next->xorptr) : NULL, __prev = __item ? JH_XOR_LIST_XOR(__item->xorptr, __next) : __prev)

/**
 * 
 * @par Description:
 * 反向遍历链表
 * 
 * @param item  结点名
 * @param list  链表头
 * 
 * @retval None.
 * 
 */
#define JH_XOR_LIST_FOR_EACH_REVERSE(__item, __list)                                        \
    for (jh_xor_list_t *__item = (__list)->tail, *__prev = NULL, *__tmp;                    \
         __item != NULL;                                                                    \
         __tmp = __item, __item = JH_XOR_LIST_XOR(__item->xorptr, __prev), __prev = __tmp)

/**
 * 
 * @par Description:
 * 安全的反向遍历链表，可以在遍历中添加与删除结点
 * 
 * @param item  结点名
 * @param list  链表头
 * 
 * @retval None.
 * 
 */
#define JH_XOR_LIST_FOR_EACH_SAFE_REVERSE(__item, __list)                                                                                                                                                   \
    for (jh_xor_list_t *__item = (__list)->tail, *__prev = NULL, *__next = __item ? JH_XOR_LIST_XOR(__item->xorptr, NULL) : NULL, *__nextnext = __next ? JH_XOR_LIST_XOR(__next->xorptr, __item) : NULL;    \
         __item != NULL;                                                                                                                                                                                    \
         __item = __next, __next = __nextnext, __nextnext = __next ? JH_XOR_LIST_XOR(__next->xorptr, __item) : NULL, __prev = __item ? JH_XOR_LIST_XOR(__item->xorptr, __next) : __prev)

/**
 * 
 * @par Description:
 * 遍历链表获取数据
 * 
 * @param item      数据指针
 * @param list      链表头
 * @param member    数据成员名称
 * 
 * @retval None.
 * 
 */
#define JH_XOR_LIST_FOR_EACH_ENTRY(__item, __list, __member)                                        \
    for (jh_xor_list_t *__itemptr = (__list)->head, *__prev = NULL, *__tmp;                         \
         __item = JH_XOR_LIST_ENTRY(__itemptr, typeof(*__item), __member), __itemptr != NULL;       \
         __tmp = __itemptr, __itemptr = JH_XOR_LIST_XOR(__prev, __itemptr->xorptr), __prev = __tmp)

/**
 * 
 * @par Description:
 * 安全的遍历链表获取数据，可以在遍历中添加与删除结点
 * 
 * @param item      数据指针
 * @param list      链表头
 * @param member    数据成员名称
 * 
 * @retval None.
 * 
 */
#define JH_XOR_LIST_FOR_EACH_ENTRY_SAFE(__item, __list, __member)                                                                                                                                                       \
    for (jh_xor_list_t *__itemptr = (__list)->head, *__prev = NULL, *__next = __itemptr ? JH_XOR_LIST_XOR(NULL, __itemptr->xorptr) : NULL, *__nextnext = __next ? JH_XOR_LIST_XOR(__itemptr, __next->xorptr) : NULL;    \
         __item = JH_XOR_LIST_ENTRY(__itemptr, typeof(*__item), __member), __itemptr != NULL;                                                                                                                           \
         __itemptr = __next, __next = __nextnext, __nextnext = __next ? JH_XOR_LIST_XOR(__itemptr, __next->xorptr) : NULL, __prev = __itemptr ? JH_XOR_LIST_XOR(__itemptr->xorptr, __next) : __prev)

/**
 * 
 * @par Description:
 * 反向遍历链表获取数据
 * 
 * @param item      数据指针
 * @param list      链表头
 * @param member    数据成员名称
 * 
 * @retval None.
 * 
 */
#define JH_XOR_LIST_FOR_EACH_ENTRY_REVERSE(__item, __list, __member)                                \
    for (jh_xor_list_t *__itemptr = (__list)->tail, *__prev = NULL, *__tmp;                         \
         __item = JH_XOR_LIST_ENTRY(__itemptr, typeof(*__item), __member), __itemptr != NULL;       \
         __tmp = __itemptr, __itemptr = JH_XOR_LIST_XOR(__itemptr->xorptr, __prev), __prev = __tmp)

/**
 * 
 * @par Description:
 * 安全的反向遍历链表获取数据，可以在遍历中添加与删除结点
 * 
 * @param item      数据指针
 * @param list      链表头
 * @param member    数据成员名称
 * 
 * @retval None.
 * 
 */
#define JH_XOR_LIST_FOR_EACH_ENTRY_SAFE_REVERSE(__item, __list, __member)                                                                                                                                               \
    for (jh_xor_list_t *__itemptr = (__list)->tail, *__prev = NULL, *__next = __itemptr ? JH_XOR_LIST_XOR(NULL, __itemptr->xorptr) : NULL, *__nextnext = __next ? JH_XOR_LIST_XOR(__itemptr, __next->xorptr) : NULL;    \
         __item = JH_XOR_LIST_ENTRY(__itemptr, typeof(*__item), __member), __itemptr != NULL;                                                                                                                           \
         __itemptr = __next, __next = __nextnext, __nextnext = __next ? JH_XOR_LIST_XOR(__itemptr, __next->xorptr) : NULL, __prev = __itemptr ? JH_XOR_LIST_XOR(__itemptr->xorptr, __next) : __prev)

/**
 * 
 * @par Description:
 * 查看链表头的数据
 * 
 * @attention
 * None.
 * 
 * @param list      链表头
 * @param type      定义的数据结构
 * @param member    数据成员名称
 * 
 * @retval 数据地址.
 * 
 */
#define JH_XOR_LIST_PEEK_HEAD_TYPE(__list, __type, __member) ({     \
    __type *__t;                                                    \
    if ((__list)->head == NULL) {                                   \
        __t = NULL;                                                 \
    } else {                                                        \
        __t = JH_XOR_LIST_ENTRY((__list)->head, __type, __member);  \
    }                                                               \
    __t;                                                            \
})

/**
 * 
 * @par Description:
 * 查看链表尾的数据
 * 
 * @attention
 * None.
 * 
 * @param list      链表头
 * @param type      定义的数据结构
 * @param member    数据成员名称
 * 
 * @retval 数据地址.
 * 
 */
#define JH_XOR_LIST_PEEK_TAIL_TYPE(__list, __type, __member) ({     \
    __type *__t;                                                    \
    if ((__list)->tail == NULL) {                                   \
        __t = NULL;                                                 \
    } else {                                                        \
        __t = JH_XOR_LIST_ENTRY((__list)->tail, __type, __member);  \
    }                                                               \
    __t;                                                            \
})

/**
 * 
 * @par Description:
 * 获取链表头的数据，并从链表中删除结点
 * 
 * @param list      链表头
 * @param type      定义的数据结构
 * @param member    数据成员名称
 * 
 * @retval 数据地址.
 * 
 */
#define JH_XOR_LIST_REMOVE_HEAD_TYPE(__list, __type, __member) ({   \
    __type *__t;                                                    \
    if ((__list)->head == NULL) {                                   \
        __t = NULL;                                                 \
    } else {                                                        \
        __t = JH_XOR_LIST_ENTRY((__list)->head, __type, __member);  \
        jha_xor_list_remove_head(__list);                           \
    }                                                               \
    __t;                                                            \
})

/**
 * 
 * @par Description:
 * 获取链表尾的数据，并从链表中删除结点
 * 
 * @param list      链表头
 * @param type      定义的数据结构
 * @param member    数据成员名称
 * 
 * @retval 数据地址.
 * 
 */
#define JH_XOR_LIST_REMOVE_TAIL_TYPE(__list, __type, __member) ({   \
    __type *__t;                                                    \
    if ((__list)->tail == NULL) {                                   \
        __t = NULL;                                                 \
    } else {                                                        \
        __t = JH_XOR_LIST_ENTRY((__list)->tail, __type, __member);  \
        jha_xor_list_remove_tail(__list);                           \
    }                                                               \
    __t;                                                            \
})

#endif